package cn.aylog.example;

import java.util.*;

/**
 * 贪心算法解决覆盖问题
 */
public class GreedyToCover {
    public static void main(String[] args) {
        Map<String, Set<String>> broads = new HashMap<>();
        Set<String> k1 = new HashSet<>();
        k1.add("北京");
        k1.add("上海");
        k1.add("天津");
        Set<String> k2 = new HashSet<>();
        k2.add("广州");
        k2.add("北京");
        k2.add("深圳");
        Set<String> k3 = new HashSet<>();
        k3.add("成都");
        k3.add("上海");
        k3.add("杭州");
        Set<String> k4 = new HashSet<>();
        k4.add("上海");
        k4.add("天津");
        Set<String> k5 = new HashSet<>();
        k5.add("杭州");
        k5.add("大连");
        broads.put("k1", k1);
        broads.put("k2", k2);
        broads.put("k3", k3);
        broads.put("k4", k4);
        broads.put("k5", k5);
        greedy(broads);
    }

    public static void greedy(Map<String, Set<String>> broads) {
        List<String> list = new ArrayList<>();
        Set<String> allCity = new HashSet<>();
        // 遍历获取所有的城市
        for(Map.Entry<String, Set<String>> entry : broads.entrySet()) {
            allCity.addAll(entry.getValue());
        }
        int max = 0;
        String maxKey = "";
        while(!allCity.isEmpty()) {
            // 贪心算法, 每次遍历获取匹配最多的未覆盖的城市的电台
            for(Map.Entry<String, Set<String>> entry : broads.entrySet()) {
                Iterator<String> it = entry.getValue().iterator();
                int tmp = 0;
                // 统计覆盖多少个未覆盖的城市
                while (it.hasNext()) {
                    String val = it.next();
                    if(allCity.contains(val)) {
                        tmp++;
                    }
                }
                // allCity.retainAll(entry.getValue()); // 获取两个集合的交集
                // 保存最大的匹配值
                if(tmp > max) {
                    max = tmp;
                    maxKey = entry.getKey();
                }
            }
            // 将当前最大的匹配保存,将已经覆盖的城市移除
            allCity.removeAll(broads.get(maxKey));
            list.add(maxKey);
            max = 0;
        }
        System.out.println(list);
    }
}
